package myDoubleLinkList;


import java.util.Stack;

//无头双向非循环链表模拟实现
public class DoubleLinkList {
    //给双向链表抽象一个节点类
    static class listNode {
        //节点的数值域
        public int val;
        //节点的前驱节点
        public listNode pre;
        //节点的后驱节点
        public listNode next;
        //构造节点的构造方法

        public listNode(int val) {
            this.val = val;
        }
    }

    //双向链表的头节点
    public listNode head;
    //双向链表的尾节点
    public listNode last;


    ////////双向链表的重点方法//////
    // 2、无头双向链表实现
        //头插法
        public void addFirst(int data) {
            listNode newNode=new listNode(data);
            //判断是否为第一次插入数据
            if(head==last&&head==null){
                head=newNode;
                last=newNode;
            }else{
                head.pre=newNode;
                newNode.next=head;
                head=newNode;
            }
        }

        //尾插法
        public void addLast(int data) {
            listNode newNode=new listNode(data);
            //判断是否为第一次插入数据
            if(head==last&&head==null){
                head=newNode;
                last=newNode;
            }else{
                last.next=newNode;
                newNode.pre=last;
                last=newNode;
            }
        }

        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index, int data) {
            //判断下标合法性
            if(index<0||index>size()){
                throw new DMyDoubleLinkIndexException("插入下标非法");
            }
            //判断是否可以为头插
            if(index==0){
                addFirst(data);
            }
            //判断是否可以为尾插
            if(index==size()){
                addLast(data);
            }

            listNode newNode=new listNode(data);
            listNode cur=head;
            //找到index下标的节点
            //与单链表的此方法不一样，单链表是无法知道某个节点的前一个
            //节点是谁,所以单链表情况下要先找到index下标节点的前一个节点
            //而双向链表则不用，因为它是可以知道某个节点的前一个节点是谁的
            while(index>0){
                cur=cur.next;
                index--;
            }
            //此时cur已经找到了index下标的节点
            cur.pre.next=newNode;
            newNode.pre=cur.pre;
            newNode.next=cur;
            cur.pre=newNode;
        }

        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key) {
            listNode cur=head;
            while(cur!=null){
               if(cur.val==key){
                   return true;
               }
                cur=cur.next;
            }
            return false;
        }

        //删除第一次出现关键字为key的节点
        public void remove(int key) {
            if(head==null){
                System.out.println("空链表无法删除");
                return;
            }
            listNode cur=head;
            while(cur!=null) {
                if(cur.val==key){
                    //判断是否为头节点
                    if(cur==head){
                        head=head.next;
                        //排除链表只有一个节点的情况
                        if(head!=null){
                            head.pre=null;
                        }
                        return;
                    }else{
                        cur.pre.next=cur.next;
                        //排除当前节点为最后一个节点的情况
                        if(cur.next!=null){
                            cur.next.pre=cur;
                        }
                        return;
                    }
                }
                cur=cur.next;
            }


        }

        //删除所有值为key的节点
        public void removeAllKey(int key) {
            if(head==null){
                System.out.println("空链表无法删除");
                return;
            }
            listNode cur=head;
            while(cur!=null) {
                if(cur.val==key){
                    //判断是否为头节点
                    if(cur==head){
                        head=head.next;
                        //排除链表只有一个节点的情况
                        if(head!=null){
                            head.pre=null;
                        }
                    }else{
                        cur.pre.next=cur.next;
                        //排除当前节点为最后一个节点的情况
                        if(cur.next!=null){
                            cur.next.pre=cur;
                        }
                    }
                }
                cur=cur.next;
            }
        }

        //得到单链表的长度
        public int size() {
            int size=0;
            listNode cur=head;
            while(cur!=null){
                size++;
                cur=cur.next;
            }
            return size;
        }

        //打印双向链表中的所有节点
        public void display() {
            listNode cur=head;
            while(cur!=null){
                System.out.print(cur.val+" ");
                cur=cur.next;
            }
            System.out.println();
        }

/////3545
        public void clear() {
            listNode cur=head;
            while(cur!=null){
                listNode curNext=cur.next;
                if(cur==head){
                    cur.next=null;
                    cur=curNext;
                    continue;
                }

                cur.pre=null;
                cur.next=null;
                cur=curNext;
            }
            head=null;
            last=null;
        }

    public listNode getHead() {
        return head;
    }

    //递归逆序打印链表
        public void printLast1(listNode root){
            if(root==null)return;
            printLast1(root.next);
            System.out.print(root.val+" ");
        }
        //使用栈逆序打印链表
    public static Stack<listNode> stack=new Stack<>();
    public void printLast(){
            listNode cur=head;
            //将所有节点存储到栈中
            while(cur!=null){
                stack.push(cur);
                cur=cur.next;
            }
            //将栈中所有元素弹出并打印(逆序)
            while(!stack.isEmpty()){
                System.out.print(stack.pop().val+" ");
            }
    }

}
